{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #早餐组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: breakfastNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #早餐组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣在秋日市集选择了一家早餐摊位，一维整型数组 `staple` 中记录了每种主食的价格，一维整型数组 `drinks` 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 `x` 元。请返回小扣共有多少种购买方案。\r\n",
    "\r\n",
    "注意：答案需要以 `1e9 + 7 (1000000007)` 为底取模，如：计算初始结果为：`1000000008`，请返回 `1`\r\n",
    "\r\n",
    "**示例 1：**\r\n",
    ">输入：`staple = [10,20,5], drinks = [5,5,2], x = 15`\r\n",
    ">\r\n",
    ">输出：`6`\r\n",
    ">\r\n",
    ">解释：小扣有 6 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：\r\n",
    ">第 1 种方案：staple[0] + drinks[0] = 10 + 5 = 15；\r\n",
    ">第 2 种方案：staple[0] + drinks[1] = 10 + 5 = 15；\r\n",
    ">第 3 种方案：staple[0] + drinks[2] = 10 + 2 = 12；\r\n",
    ">第 4 种方案：staple[2] + drinks[0] = 5 + 5 = 10；\r\n",
    ">第 5 种方案：staple[2] + drinks[1] = 5 + 5 = 10；\r\n",
    ">第 6 种方案：staple[2] + drinks[2] = 5 + 2 = 7。\r\n",
    "\r\n",
    "**示例 2：**\r\n",
    ">输入：`staple = [2,1,1], drinks = [8,9,5,1], x = 9`\r\n",
    ">\r\n",
    ">输出：`8`\r\n",
    ">\r\n",
    ">解释：小扣有 8 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：\r\n",
    ">第 1 种方案：staple[0] + drinks[2] = 2 + 5 = 7；\r\n",
    ">第 2 种方案：staple[0] + drinks[3] = 2 + 1 = 3；\r\n",
    ">第 3 种方案：staple[1] + drinks[0] = 1 + 8 = 9；\r\n",
    ">第 4 种方案：staple[1] + drinks[2] = 1 + 5 = 6；\r\n",
    ">第 5 种方案：staple[1] + drinks[3] = 1 + 1 = 2；\r\n",
    ">第 6 种方案：staple[2] + drinks[0] = 1 + 8 = 9；\r\n",
    ">第 7 种方案：staple[2] + drinks[2] = 1 + 5 = 6；\r\n",
    ">第 8 种方案：staple[2] + drinks[3] = 1 + 1 = 2；\r\n",
    "\r\n",
    "**提示：**\r\n",
    "+ `1 <= staple.length <= 10^5`\r\n",
    "+ `1 <= drinks.length <= 10^5`\r\n",
    "+ `1 <= staple[i],drinks[i] <= 10^5`\r\n",
    "+ `1 <= x <= 2*10^5`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [2vYnGI](https://leetcode.cn/problems/2vYnGI/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [2vYnGI](https://leetcode.cn/problems/2vYnGI/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,20,5]\\n[5,5,2]\\n15', '[2,1,1]\\n[8,9,5,1]\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "\n",
    "        for s in staple:\n",
    "            if s > x:\n",
    "                break\n",
    "            while drinks and drinks[-1] + s > x:\n",
    "                drinks.pop()\n",
    "            ans += len(drinks)\n",
    "\n",
    "        return ans % 1000000007\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        m=max(drinks)\n",
    "        cnt=[0]*(m+1)\n",
    "        for i in drinks:\n",
    "            cnt[i]+=1\n",
    "        for i in range(1,m+1):\n",
    "            cnt[i]+=cnt[i-1]\n",
    "        ans=0\n",
    "        for s in staple:\n",
    "            k=x-s\n",
    "            if k>=m:\n",
    "                ans+=cnt[m]\n",
    "            elif k>0:\n",
    "                ans+=cnt[k]\n",
    "            ans%=1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        staple.sort()\n",
    "\n",
    "        drinks.sort()\n",
    "\n",
    "        for s in staple:\n",
    "            if s > x:\n",
    "                break\n",
    "            while drinks and drinks[-1] + s > x:\n",
    "                drinks.pop()\n",
    "            ans += len(drinks)\n",
    "\n",
    "        return ans % 1000000007\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: list[int], drinks: list[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        # drinks.reverse()\n",
    "        count = 0\n",
    "        tmp=0\n",
    "        for i in range(len(staple)):\n",
    "            while drinks and staple[i]+drinks[-1] > x:\n",
    "                drinks.pop()\n",
    "            count += len(drinks)\n",
    "        return count % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple = [i for i in staple if i < x]\n",
    "        drinks = [i for i in drinks if i < x]\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        count = 0\n",
    "        drinks_len = len(drinks)\n",
    "        for i in staple:\n",
    "            if i >= x or drinks_len==0:\n",
    "                break\n",
    "            while i + drinks[drinks_len - 1] > x:\n",
    "                drinks_len -= 1\n",
    "                if drinks_len == 0:\n",
    "                    break\n",
    "            count += drinks_len\n",
    "            count %= 1000000007\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        L_staple = len(staple)\n",
    "        L_drinks = len(drinks)\n",
    "        for i in range(L_staple):\n",
    "            if staple[L_staple-1-i] >= x:\n",
    "                del staple[L_staple-1-i]\n",
    "        for i in range(L_drinks):\n",
    "            if drinks[L_drinks-1-i] >= x:\n",
    "                del drinks[L_drinks-1-i]\n",
    "        \n",
    "        staple = sorted(staple)\n",
    "        drinks = sorted(drinks)\n",
    "    \n",
    "        if len(staple) * len(drinks) == 0:\n",
    "            return 0\n",
    "\n",
    "        if staple[0] + drinks[0] > x:\n",
    "            return 0\n",
    "        \n",
    "        k = -1\n",
    "        while k < len(drinks)-1 and drinks[k+1] <= x - staple[0]:\n",
    "            k += 1\n",
    "\n",
    "        res = k+1 \n",
    "        \n",
    "        for i in range(1, len(staple)):\n",
    "            if staple[i] == staple[i-1]:\n",
    "                res += (k+1)\n",
    "            elif staple[i] + drinks[0] > x:\n",
    "                return res \n",
    "            else:\n",
    "                while k >= 0 and drinks[k] > x - staple[i]:\n",
    "                    k -= 1\n",
    "                res += (k+1) \n",
    "        return res%(1000000007)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "        \n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "        \n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "        \n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "            \n",
    "        return ans % (10 ** 9 + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        m=len(staple)\n",
    "        n=len(drinks)\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        i,j=0,n-1\n",
    "        res=0\n",
    "        while i<m and j>=0:\n",
    "            total=staple[i]+drinks[j]\n",
    "            if total<=x:\n",
    "                i+=1\n",
    "                res+=j+1\n",
    "                res%=1000000007\n",
    "            else:\n",
    "                j-=1\n",
    "        return res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        count = 0\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        second = len(drinks)-1\n",
    "        for first in range(len(staple)):\n",
    "            while second >= 0 and staple[first] + drinks[second] > x:\n",
    "                second -= 1\n",
    "            if staple[first] + drinks[second] <= x:\n",
    "                count += (second+1)\n",
    "                \n",
    "        return (count % 1000000007)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        ans = 0\n",
    "        for s in staple:\n",
    "            if s < x:\n",
    "                ans += bisect.bisect_right(drinks, x-s)\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        y = 0\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        i,j = 0,len(drinks) - 1\n",
    "        while i < len(staple) and j >= 0:\n",
    "            if staple[i] + drinks[j] > x:\n",
    "                j = j - 1\n",
    "            else:\n",
    "                y = y + (j+1)\n",
    "                i = i + 1 \n",
    "                y %= 1000000007\n",
    "\n",
    "        return y\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "\n",
    "        s1, d1 = 0, len(drinks)-1\n",
    "        result = 0\n",
    "\n",
    "        # for s1 in range(len(staple)):\n",
    "        #     while d1 >= 0:\n",
    "        #         if (staple[s1]+drinks[d1]) <= x:\n",
    "        #             result += (d1+1)\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             d1 -= 1\n",
    "        \n",
    "        while (s1 < len(staple)) and  (d1 >= 0):\n",
    "            if (staple[s1]+drinks[d1]) <= x:\n",
    "                result += (d1+1)\n",
    "                s1 += 1\n",
    "            else:\n",
    "                d1 -= 1\n",
    "        \n",
    "        return result%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        def find(drinks: List[int], money: int) -> int:\n",
    "            left, right = 0, len(drinks)-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if drinks[mid] > money:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        drinks.sort()\n",
    "        ans = 0\n",
    "        for money in staple:\n",
    "            if money >= x:\n",
    "                continue\n",
    "            ans += find(drinks, x - money) % 1000000007\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        res = 0\n",
    "        j = len(drinks) - 1\n",
    "        res = 0\n",
    "        for i in staple:\n",
    "            while j > 0 and drinks[j] + i  > x:\n",
    "                j -= 1\n",
    "            if drinks[j] + i <= x:\n",
    "                res += j + 1\n",
    "        return res % 1000000007\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "\n",
    "        s1, d1 = 0, len(drinks)-1\n",
    "        result = 0\n",
    "\n",
    "        for s1 in range(len(staple)):\n",
    "            while d1 >= 0:\n",
    "                if (staple[s1]+drinks[d1]) <= x:\n",
    "                    result += (d1+1)\n",
    "                    break\n",
    "                else:\n",
    "                    d1 -= 1\n",
    "        \n",
    "        return result%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "\n",
    "        s1, d1 = 0, len(drinks)-1\n",
    "        result = 0\n",
    "\n",
    "        # for s1 in range(len(staple)):\n",
    "        #     while d1 >= 0:\n",
    "        #         if (staple[s1]+drinks[d1]) <= x:\n",
    "        #             result += (d1+1)\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             d1 -= 1\n",
    "        \n",
    "        while (s1 < len(staple)) and  (d1 >= 0):\n",
    "            if (staple[s1]+drinks[d1]) <= x:\n",
    "                result += (d1+1)\n",
    "                s1 += 1\n",
    "            else:\n",
    "                d1 -= 1\n",
    "        \n",
    "        return result%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple=sorted(staple)\n",
    "        drinks=sorted(drinks)\n",
    "        left=0\n",
    "        right=len(drinks)-1\n",
    "        count=0\n",
    "        while left<len(staple) and right>=0:\n",
    "            if staple[left]+drinks[right]>x:\n",
    "                right-=1\n",
    "            else:\n",
    "                count+=right+1\n",
    "                left+=1\n",
    "        return int(count%(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple=sorted(staple)\n",
    "        drinks=sorted(drinks)\n",
    "        left=0\n",
    "        right=len(drinks)-1\n",
    "        count=0\n",
    "        while left<len(staple) and right>=0:\n",
    "            if staple[left]+drinks[right]>x:\n",
    "                right-=1\n",
    "            else:\n",
    "                count+=right+1\n",
    "                left+=1\n",
    "        return int(count%(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        \n",
    "        drinks.sort()\n",
    "        min_drink = drinks[0]\n",
    "        staple.sort()\n",
    "        n = len(drinks)-1\n",
    "        j = n\n",
    "        ans=0\n",
    "        for food in staple:\n",
    "            # j=n 关键就在这里 不用每次重新搜索 food 变大可能的drink必然变少\n",
    "            while j>=0 and drinks[j]>(x-food) :\n",
    "                j-=1\n",
    "            if drinks[j] + food <= x:\n",
    "                ans += (j+1) # 索引数量+1 == 真数量                \n",
    "\n",
    "        return int(ans % (1e9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        res=0\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        cur=len(drinks)-1\n",
    "        for i,s in enumerate(staple):\n",
    "            while cur>-1 and drinks[cur]>x-s:\n",
    "                cur-=1\n",
    "            res+=cur+1\n",
    "            if cur==-1:break\n",
    "        return res%(int(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "\n",
    "        staple.sort(key = lambda x: x)\n",
    "        drinks.sort(key = lambda x: x)\n",
    "        i, j = 0, len(drinks)-1\n",
    "        n = len(staple)\n",
    "        ans = 0\n",
    "        while i < n and j > -1:\n",
    "            sum = staple[i] + drinks[j]\n",
    "            if sum <= x:\n",
    "                ans += j + 1\n",
    "                i += 1\n",
    "                ans %= 1000000007\n",
    "            else:\n",
    "                j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        res=0\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        p_staple=0\n",
    "        p_drinks=len(drinks)-1\n",
    "        while p_staple<len(staple) and p_drinks>=0:\n",
    "            if staple[p_staple]+drinks[p_drinks]<=x:\n",
    "                res+=p_drinks+1\n",
    "                p_staple+=1\n",
    "            else:\n",
    "                p_drinks-=1\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        l=0\n",
    "        r=len(drinks)-1\n",
    "        ans=0\n",
    "        while l<len(staple) and r>=0:\n",
    "            if staple[l]+drinks[r]>x:\n",
    "                r-=1\n",
    "            else:\n",
    "                l+=1\n",
    "                ans+=r+1\n",
    "        return ans%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        staple_ = sorted(staple)\n",
    "        drinks_ = sorted(drinks)\n",
    "        for s in staple_:\n",
    "            d = x - s\n",
    "            if d <= 0:\n",
    "                continue\n",
    "            left = 0\n",
    "            right = len(drinks_) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if drinks_[mid] <= d:\n",
    "                    left = mid + 1\n",
    "                elif drinks_[mid] > d:\n",
    "                    right = mid - 1\n",
    "            ans += (right + 1)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple = sorted(staple)\n",
    "        drinks = sorted(drinks)\n",
    "        res = 0\n",
    "        for s in staple:\n",
    "            res += bisect_right(drinks, x-s)\n",
    "        return int(res % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        if min(staple) >= x and min(drinks)>= x:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        staple_len = bisect_right(staple, x - drinks[0])\n",
    "        \n",
    "        for sta in staple[:staple_len]:            \n",
    "                # 二分查找\n",
    "                target = x - sta\n",
    "                index = bisect_right(drinks, target)\n",
    "                ans += index\n",
    "        \n",
    "        return ans % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        res = 0\n",
    "        i,j = 0,len(drinks)-1\n",
    "        while i < len(staple) and j >= 0:\n",
    "            if staple[i] + drinks[j] > x:\n",
    "                j -= 1\n",
    "            else:\n",
    "                res += (j+1)\n",
    "                res %= 1000000007\n",
    "                i += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "print(Solution().breakfastNumber([10,20,5],[5,5,2],15))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        drinks_ = sorted(drinks)\n",
    "        for s in staple:\n",
    "            d = x - s\n",
    "            if d <= 0:\n",
    "                continue\n",
    "            left = 0\n",
    "            right = len(drinks_) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if drinks_[mid] <= d:\n",
    "                    left = mid + 1\n",
    "                elif drinks_[mid] > d:\n",
    "                    right = mid - 1\n",
    "            ans += (right + 1)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        num = 0\n",
    "        j = len(drinks) - 1\n",
    "        for i in staple:\n",
    "            # 遍历找到第一个\n",
    "            while j >= 0 and i + drinks[j] > x:\n",
    "                j = j - 1\n",
    "            if i + drinks[j] <= x:\n",
    "                num = num + j + 1\n",
    "        return num % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple = sorted(staple)\n",
    "        drinks = sorted(drinks)\n",
    "        print(drinks)\n",
    "        res = 0\n",
    "        for i in staple:\n",
    "            a,b,j = 0,len(drinks)-1,0\n",
    "            while a<b and b<len(drinks):\n",
    "                j = (a+b)//2+1\n",
    "                if (i+drinks[j])>x:\n",
    "                    b = j-1\n",
    "                elif (i+drinks[j])<=x:\n",
    "                    a = j+1\n",
    "            print(a)\n",
    "            if a<len(drinks) and drinks[a]+i<=x:\n",
    "                res += a+1\n",
    "            else:\n",
    "                res += a\n",
    "        return res%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        res = 0\n",
    "        i = bisect_right(staple, x - drinks[0])\n",
    "        for j in staple[:i]:\n",
    "            res += bisect_right(drinks, x - j)\n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple=sorted(staple)\n",
    "        drinks=sorted(drinks)\n",
    "\n",
    "        re=0\n",
    "        i=0\n",
    "        j=len(drinks)-1\n",
    "\n",
    "        while i<len(staple) and j>=0:\n",
    "            if staple[i]+drinks[j]<=x:\n",
    "                re+=j+1\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "\n",
    "        return re % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        ans=0\n",
    "        tmp=x-staple[0]\n",
    "        flag=False\n",
    "        for i in range(len(drinks)):\n",
    "            if drinks[i]<=tmp:\n",
    "                ans+=1\n",
    "            else:\n",
    "                right=i\n",
    "                flag=True\n",
    "            if not flag:\n",
    "                right=i+1\n",
    "        # print(ans)\n",
    "        staple=staple[1:]\n",
    "        drinks=drinks[:right]\n",
    "        # print(staple,drinks)\n",
    "        n=len(drinks)-1        \n",
    "        for s in staple:\n",
    "            if s>x:\n",
    "                break\n",
    "            tmp=x-s            \n",
    "            while drinks[n]>tmp and n>=0:\n",
    "                n-=1\n",
    "            ans+=n+1\n",
    "        return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        mod = 1000000007 # 用于取模计算\n",
    "        n, m = len(staple), len(drinks) # 获取主食和饮料的数量\n",
    "        res = 0 # 统计购买方案数\n",
    "        # 将主食和饮料按升序排序\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        i, j = 0, m - 1 # i指向主食的开头，j指向饮料的结尾\n",
    "        while i < n and j >= 0:\n",
    "            if staple[i] + drinks[j] <= x:\n",
    "                res = (res + j + 1) % mod # 更新购买方案数\n",
    "                i += 1 # 将主食指针向右移动\n",
    "            else:\n",
    "                j -= 1 # 将饮料指针向左移动\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        drinks.sort()\n",
    "        res = 0\n",
    "        for i in range(len(staple)):\n",
    "            l , r = 0, len(drinks) - 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if staple[i] + drinks[mid] >x:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid +1\n",
    "            res += l\n",
    "        return res % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        \n",
    "        ans = 0 \n",
    "        s = sorted(staple)\n",
    "        d = sorted(drinks)\n",
    "        i = 0 \n",
    "        j = len(d)-1\n",
    "        while i < len(s) and j > -1:\n",
    "            if s[i] + d[j] <= x: \n",
    "                ans += (j+1)\n",
    "                i += 1 \n",
    "            else: \n",
    "                j -= 1 \n",
    "        return ans%1000000007\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        a=0\n",
    "        arr=[0]*x\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        for i in staple:\n",
    "            if i<x:\n",
    "                arr[i]+=1\n",
    "            else:\n",
    "                break\n",
    "        for j in range(2,x):\n",
    "            arr[j]+=arr[j-1]\n",
    "        for j in drinks:\n",
    "            c=x-j\n",
    "            if c<=0:\n",
    "                break\n",
    "            a+=arr[c]\n",
    "        return a%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        #时间复杂度为：O(nlogn)\n",
    "        from bisect import bisect_right\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        ans=0\n",
    "        for i in range(len(staple)):\n",
    "            A=staple[i]\n",
    "            target=x-A\n",
    "            if target<1:\n",
    "                continue\n",
    "            #二分找<=target的最大的数的索引\n",
    "            b=bisect_right(drinks,target)-1\n",
    "            ans+=b+1\n",
    "        return ans%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        ans,m=0,0\n",
    "        for i in range(len(staple)-1,-1,-1):\n",
    "            if staple[i]>=x:continue    \n",
    "            while m<len(drinks) and drinks[m]+staple[i]<=x:\n",
    "                m+=1\n",
    "            ans+=m\n",
    "        return ans%1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        if len(staple) < len(drinks):\n",
    "            return self.breakfastNumber(drinks, staple, x)\n",
    "        count = 0\n",
    "        drinks.sort()\n",
    "        for i in range(len(staple)):\n",
    "            j = bisect.bisect_right(drinks, x - staple[i])\n",
    "            count += j\n",
    "        return count % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        mod = 1000000007\n",
    "        count = 0\n",
    "        staple.sort()\n",
    "        drinks.sort(reverse=True)\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(staple) and j < len(drinks):\n",
    "            if staple[i] + drinks[j] > x:\n",
    "                j += 1\n",
    "            else:\n",
    "                count += (len(drinks) - j)\n",
    "                count %= mod\n",
    "                i += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        num = 0\n",
    "        # preSum[i]: 价格小于等于i的staple个数\n",
    "        preSum = [0] * (x + 1)\n",
    "        for s in staple:\n",
    "            if s <= x:\n",
    "                preSum[s] += 1\n",
    "        # 题目规定staple[i] >= 1则preSum[0]为0, 不需要更新preSum[1]\n",
    "        for i in range(2, x + 1):\n",
    "            preSum[i] += preSum[i - 1]\n",
    "        for d in drinks:\n",
    "            if x - d > 0:\n",
    "                num += preSum[x - d]\n",
    "        return num % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        cnt=0\n",
    "        for s in staple:\n",
    "            if s>= x:\n",
    "                break\n",
    "            cnt+=bisect_right(drinks,x-s)\n",
    "            cnt%=MOD\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        num = 0\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        m, n = len(staple), len(drinks)\n",
    "        i, j = 0, n - 1\n",
    "        while i < m and j >= 0:\n",
    "            if staple[i] + drinks[j] <= x:\n",
    "                # staple[i]和drinks[:j+1]配对\n",
    "                num += j + 1\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return num % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        mod = 1000000007\n",
    "        # > 输入：`staple = [10,20,5], drinks = [5,5,2], x = 15`\n",
    "        # >\n",
    "        # > 输出：`6`\n",
    "        # 5 10 20\n",
    "        # 2 5 10\n",
    "        ans = 0\n",
    "\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        for s in staple:\n",
    "            if s >= x: break\n",
    "            l, r = 0, len(drinks) - 1\n",
    "            while l <= r:\n",
    "                m = (l + r) // 2\n",
    "                if s + drinks[m] <= x:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            ans += l\n",
    "\n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        result = 0\n",
    "        list_ = [0 for i in range(x+1)]\n",
    "        for i in staple:\n",
    "            if i < x:\n",
    "                list_[i] += 1\n",
    "\n",
    "        for i in range(2, x):\n",
    "            list_[i] += list_[i-1]\n",
    "\n",
    "        for j in drinks:\n",
    "            temp = x - j\n",
    "            if temp < 0:\n",
    "                pass\n",
    "            else:\n",
    "                result += list_[temp]\n",
    "        return int(result % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        num = 0\n",
    "        j = len(drinks) - 1\n",
    "        for i in staple:\n",
    "            num = num + self.binsearch(drinks, x - i)\n",
    "        return num % 1000000007\n",
    "\n",
    "\t# 二分查找\n",
    "    def binsearch(self, drinks: List[int], x: int) -> int:\n",
    "        l, r = 0, len(drinks) - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if drinks[mid] > x:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort(reverse=True)\n",
    "        drinks.sort()\n",
    "        ld = len(drinks)\n",
    "\n",
    "        print(staple)\n",
    "        inx = 0\n",
    "        a = 0\n",
    "        for i in staple:\n",
    "            if i >= x:\n",
    "                continue\n",
    "            for j in range(inx, ld):\n",
    "                if i + drinks[j] <= x:\n",
    "                    inx += 1\n",
    "                else:\n",
    "                    break\n",
    "            a += inx\n",
    "\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort(reverse=True)\n",
    "        drinks.sort()\n",
    "        # ls = len(staple)\n",
    "        ld = len(drinks)\n",
    "\n",
    "        print(staple)\n",
    "        inx = 0\n",
    "        a = 0\n",
    "        for i in staple:\n",
    "            if i >= x:\n",
    "                continue\n",
    "            for j in range(inx, ld):\n",
    "                if i + drinks[j] <= x:\n",
    "                    inx += 1\n",
    "                else:\n",
    "                    break\n",
    "            a += inx\n",
    "\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        case_num = 0\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        self.drinks = drinks\n",
    "        self.drink_limit_map = dict()\n",
    "        last_max_index = len(drinks) - 1\n",
    "        for s in staple:\n",
    "            if s >= x:\n",
    "                continue\n",
    "            drink_limit = x - s\n",
    "            max_drink_index = self.find_max_drink_index(last_max_index, drink_limit)\n",
    "            last_max_index = max_drink_index\n",
    "            if last_max_index < 0:\n",
    "                break\n",
    "            case_num += (max_drink_index + 1)\n",
    "\n",
    "        return case_num % 1000000007\n",
    "\n",
    "\n",
    "    def find_max_drink_index(self, last_max_index, drink_limit):\n",
    "        if drink_limit in self.drink_limit_map:\n",
    "            return self.drink_limit_map[drink_limit]\n",
    "        \n",
    "        pre_index = last_max_index\n",
    "        while pre_index >= 0 and self.drinks[pre_index] > drink_limit:\n",
    "            pre_index -= 1\n",
    "\n",
    "        self.drink_limit_map[drink_limit] = pre_index\n",
    "        return pre_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple=sorted(staple)\n",
    "        drinks=sorted(drinks)\n",
    "        l=[]\n",
    "        i=0\n",
    "        for a in range(drinks[-1]+1):\n",
    "            while i<len(drinks) and a==drinks[i]:\n",
    "                i+=1\n",
    "            l.append(i)\n",
    "        ans=0\n",
    "        if (x-staple[-1])>=drinks[-1]: ans=len(staple)*len(drinks)\n",
    "        else:\n",
    "            for p in staple:\n",
    "                if x<p:  break\n",
    "                elif x-p>len(l)-1:ans+=l[-1]\n",
    "                else : ans+=l[x-p]\n",
    "        return ans%(10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        count = 0\n",
    "\n",
    "        # for a in staple:\n",
    "        #     for b in drinks:\n",
    "        #         if a > x or b > x:\n",
    "        #             continue\n",
    "        #         if a + b <= x:\n",
    "        #             count += 1\n",
    "        # count = int(count % (1e9 + 7))\n",
    "\n",
    "        # staple = sorted(staple)\n",
    "        # drinks = sorted(drinks)\n",
    "        # ptr_s = bisect.bisect_right(staple, x)\n",
    "        # ptr_d = bisect.bisect_right(drinks, x)\n",
    "        # for i in range(ptr_s):\n",
    "        #     for j in range(ptr_d):\n",
    "        #         a = staple[i]\n",
    "        #         b = drinks[j]\n",
    "        #         if a + b > x:\n",
    "        #             ptr_d = j\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             count += 1\n",
    "\n",
    "        staple = sorted(staple)\n",
    "        drinks = sorted(drinks)\n",
    "        ptr_s = bisect.bisect_right(staple, x)\n",
    "        hi = len(drinks)\n",
    "        for i in range(ptr_s):\n",
    "            a = staple[i]\n",
    "            b = x - a\n",
    "            ptr_d = bisect.bisect_right(drinks, b, hi=hi)\n",
    "            count += ptr_d\n",
    "            hi = ptr_d\n",
    "\n",
    "        count = count % (1e9 + 7)\n",
    "        return int(count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        a=0\n",
    "        arr=[0 for i in range(x+1)]\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        for i in staple:\n",
    "            if i<x:\n",
    "                arr[i]+=1\n",
    "            else:\n",
    "                break\n",
    "        for j in range(2,x):\n",
    "            arr[j]+=arr[j-1]\n",
    "        for j in drinks:\n",
    "            c=x-j\n",
    "            if c<=0:\n",
    "                break\n",
    "            a+=arr[c]\n",
    "        return a%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        sum = 0\n",
    "        staple = sorted(staple)\n",
    "        drinks = sorted(drinks)\n",
    "        s = bisect.bisect_right(staple,x)\n",
    "        for i in staple[:s]:\n",
    "            j = bisect.bisect_right(drinks, x - i)\n",
    "            sum += j\n",
    "        return sum % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        res = 0\n",
    "        staple = sorted(staple)\n",
    "        drinks = sorted(drinks)\n",
    "        i,nd = 0,len(drinks)\n",
    "        while i < nd and staple[0] + drinks[i] <= x:\n",
    "            i += 1\n",
    "        # print(i)\n",
    "        i -= 1\n",
    "        for s in staple:\n",
    "            while -1< i  and s + drinks[i] > x:\n",
    "                i -= 1\n",
    "            if i <=0 and s + drinks[i]>x:\n",
    "                res += 0\n",
    "            else:\n",
    "                res += i+1\n",
    "        return res %(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        cnt = 0\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        staple = staple[:bisect.bisect_right(staple, x)]\n",
    "        drinks = drinks[:bisect.bisect_right(drinks, x)]\n",
    "        for s in staple:\n",
    "            cnt += bisect.bisect_right(drinks, x - s)% 1000000007\n",
    "        return cnt % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "        \n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "        \n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "        \n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "            \n",
    "        return ans % (10 ** 9 + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        count = 0\n",
    "        for ele in staple:\n",
    "            count = count + bisect_right(drinks, x-ele)\n",
    "        return count%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        # 排序+双指针\n",
    "        staple = sorted(staple)\n",
    "        drinks = sorted(drinks)\n",
    "        if staple[0] + drinks[0] > x:\n",
    "            return 0\n",
    "        \n",
    "        # 时间复杂度O(m+n)\n",
    "        ans = 0\n",
    "        j = len(drinks) - 1\n",
    "        for i in range(len(staple)):\n",
    "            while j >= 0:\n",
    "                if staple[i] + drinks[j] <= x:\n",
    "                    break\n",
    "                j -= 1\n",
    "            if j >= 0:\n",
    "                ans += j + 1\n",
    "                ans %= int(1e9 + 7)\n",
    "            else:\n",
    "                break\n",
    "        return ans % int(1e9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans=0\n",
    "        arr=[0]*x\n",
    "        for i in staple:\n",
    "            if i<x:\n",
    "                arr[i]+=1\n",
    "        for i in range(2,x):\n",
    "            arr[i]+=arr[i-1]\n",
    "        for i in drinks:\n",
    "            if x-i<=0:\n",
    "                continue\n",
    "            ans+=arr[x-i]\n",
    "        return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "        \n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "        \n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "        \n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "            \n",
    "        return ans % (10 ** 9 + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "        \n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "        \n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "        \n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "            \n",
    "        return ans % (10 ** 9 + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "        \n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "        \n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "        \n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "            \n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "        \n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "        \n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "        \n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "            \n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "    #     # 排序+双指针\n",
    "    #     staple = sorted(staple)\n",
    "    #     drinks = sorted(drinks)\n",
    "    #     if staple[0] + drinks[0] > x:\n",
    "    #         return 0\n",
    "        \n",
    "    #     # 时间复杂度O(m+n)\n",
    "    #     ans = 0\n",
    "    #     j = len(drinks) - 1\n",
    "    #     for i in range(len(staple)):\n",
    "    #         while j >= 0:\n",
    "    #             if staple[i] + drinks[j] <= x:\n",
    "    #                 break\n",
    "    #             j -= 1\n",
    "    #         if j >= 0:\n",
    "    #             ans += j + 1\n",
    "    #             ans %= int(1e9 + 7)\n",
    "    #         else:\n",
    "    #             break\n",
    "    #     return ans % int(1e9 + 7)\n",
    "\n",
    "    # O(m+n)\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "\n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "\n",
    "        # 因为凡是比这个价格低的一定和当前的饮料组合\n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "\n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        mod =1e9 + 7\n",
    "        staple.sort() # Sorting\n",
    "        drinks.sort()\n",
    "        i, j = 0, len(drinks)-1\n",
    "        res = 0\n",
    "        while i < len(staple) and j >= 0:\n",
    "            if staple[i] + drinks[j] > x:\n",
    "                j -= 1\n",
    "            else:\n",
    "                res += j + 1\n",
    "                i += 1\n",
    "        return int(res % mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "    #     # 排序+双指针\n",
    "    #     staple = sorted(staple)\n",
    "    #     drinks = sorted(drinks)\n",
    "    #     if staple[0] + drinks[0] > x:\n",
    "    #         return 0\n",
    "        \n",
    "    #     # 时间复杂度O(m+n)\n",
    "    #     ans = 0\n",
    "    #     j = len(drinks) - 1\n",
    "    #     for i in range(len(staple)):\n",
    "    #         while j >= 0:\n",
    "    #             if staple[i] + drinks[j] <= x:\n",
    "    #                 break\n",
    "    #             j -= 1\n",
    "    #         if j >= 0:\n",
    "    #             ans += j + 1\n",
    "    #             ans %= int(1e9 + 7)\n",
    "    #         else:\n",
    "    #             break\n",
    "    #     return ans % int(1e9 + 7)\n",
    "\n",
    "    # O(m+n)\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        ans = 0\n",
    "        arr = [0 for i in range(x+1)]\n",
    "\n",
    "        for sta in staple:\n",
    "            if sta < x:\n",
    "                arr[sta] += 1\n",
    "\n",
    "        for i in range(2, x):\n",
    "            arr[i] += arr[i-1]\n",
    "\n",
    "        for drink in drinks:\n",
    "            lt = x - drink\n",
    "            if lt <= 0:\n",
    "                continue\n",
    "            ans += arr[lt]\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 59/65---超时（my）\n",
    "# import bisect\n",
    "# from collections import Counter\n",
    "# class Solution:\n",
    "#     def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "#         scnt,dcnt=Counter(staple),Counter(drinks)\n",
    "#         staple=sorted(scnt.keys())\n",
    "#         drinks=sorted(dcnt.keys())\n",
    "#         m,n=len(staple),len(drinks)\n",
    "#         preD=[0]*(n+1)\n",
    "#         for i,k in enumerate(drinks):\n",
    "#             preD[i+1]=preD[i]+dcnt[k]\n",
    "#         i=0\n",
    "#         ans=0\n",
    "#         while i<m and staple[i]<x and drinks:\n",
    "#             tar=x-staple[i]\n",
    "#             idx=bisect.bisect_right(drinks,tar)\n",
    "#             ans=(ans+preD[idx]*scnt[staple[i]])%(10**9+7)\n",
    "#             drinks=drinks[:idx]\n",
    "#             i+=1\n",
    "#         return ans\n",
    "        \n",
    "### 网友：数组+前缀和\n",
    "class Solution:\n",
    "    def breakfastNumber(self,staple,drinks,x):\n",
    "        preS=[0]*(x)\n",
    "        ###统计staple<x的每个值出现次数 \n",
    "        for ss in staple:\n",
    "            if ss>=x:\n",
    "                continue \n",
    "            preS[ss]+=1\n",
    "        ### 对统计出的主食<x的每种取值个数按staple值递增顺序生成统计个数前缀和\n",
    "        for i in range(2,x):\n",
    "            preS[i]+=preS[i-1]\n",
    "\n",
    "        ans=0\n",
    "        for drink in drinks:\n",
    "            left=x-drink\n",
    "            if left<=0:\n",
    "                continue\n",
    "            ans+=preS[left]\n",
    "        \n",
    "        return ans%(10**9+7)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        res = 0\n",
    "        s,d = len(staple) - 1 , 0\n",
    "        while s >= 0 and d < len(drinks):\n",
    "            if staple[s] + drinks[d] <= x:\n",
    "                res += s + 1\n",
    "                d += 1\n",
    "            else:\n",
    "                s -= 1\n",
    "        return res % 1000000007\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        m,n=len(staple),len(drinks)\n",
    "        count=0\n",
    "        i=0\n",
    "        j=n-1\n",
    "\n",
    "        while i<m and j>=0:\n",
    "            if staple[i]+drinks[j]<=x:\n",
    "                count+=(j+1)\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return count%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        re = 0\n",
    "        i , j = 0 , len(drinks) - 1\n",
    "        while i < len(staple) and j >= 0:\n",
    "            if staple[i] + drinks[j] <= x:\n",
    "                re = (re + j + 1) % 1000000007\n",
    "                i += 1\n",
    "            else:\n",
    "                j-= 1\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        def binary_search(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums)\n",
    "            while left < right:\n",
    "                mid = (left + right)//2\n",
    "                if nums[mid] <= target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        def help(staple, drinks, x):\n",
    "            drinks.sort()\n",
    "            ans = 0\n",
    "            for i in staple:\n",
    "                ans = ans + binary_search(drinks, x - i)\n",
    "            return ans\n",
    "        if len(staple) < len(drinks):\n",
    "            return int(help(staple, drinks, x) % (1e9 + 7))\n",
    "        else:\n",
    "            return int(help(drinks, staple, x) % (1e9 + 7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        def binarySearch(i, j, target, nums):\n",
    "            while j - i > 3:\n",
    "                mid = (i+j) >> 1\n",
    "                if nums[mid] > target: j = mid\n",
    "                else: i = mid\n",
    "            for k in range(j, i-1, -1):\n",
    "                if nums[k] <= target:\n",
    "                    return k\n",
    "            return -1\n",
    "        res = 0\n",
    "        drinks.sort()\n",
    "        for i in staple:\n",
    "            pos = binarySearch(0, len(drinks)-1, x-i, drinks)\n",
    "            if pos != -1:\n",
    "                res += pos + 1\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        '''\n",
    "        1. if staple[i] + drinks[j] <= x: \n",
    "            说明第 i 个 staple 和 前 j+1 个 drinks 都满足条件（因为已经排序），所以这次有 j+1 个满足条件的组合；然后 i++；\n",
    "        2. if staple[i] + drinks[j] > x:\n",
    "            说明当前值过大，那么要减小和，就把 j 往前移，即 j-- ，继续找下一个满足条件的 i 和 j\n",
    "        '''\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "        m,n=len(staple),len(drinks)\n",
    "        count=0\n",
    "        i=0\n",
    "        j=n-1\n",
    "\n",
    "        while i<m and j>=0:\n",
    "            if staple[i]+drinks[j]<=x:\n",
    "                count+=(j+1)\n",
    "                i+=1\n",
    "            else:\n",
    "                j-=1\n",
    "        return count%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect \n",
    "class Solution:\n",
    "    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:\n",
    "        staple.sort()\n",
    "        drinks.sort()\n",
    "\n",
    "        ans=0\n",
    "        r=bisect.bisect_right(drinks,x-staple[0])\n",
    "\n",
    "\n",
    "        for drink in drinks[:r]:\n",
    "            y=x-drink\n",
    "            if y > 0:\n",
    "                i=bisect.bisect_right(staple,y)\n",
    "            ans=ans+i\n",
    "\n",
    "        return ans%1000000007"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
